package com.algrithom.sort;

import java.util.Arrays;

import com.util.CommonUtil;

/**
 * 堆排序 大顶堆 降序排序 小顶堆 升序排序
 */
class StackSort {
    
    private static final int VALUE_TWO = 2;
    
    public static void main(String[] args){
        Integer[] array1 = new Integer[]{1,3,4,2,1,10,5};
        heapSort(array1);
        System.out.println(Arrays.toString(array1));
    }
    
    /**
     * 堆排序
     *
     * @param array 数组
     */
    private static void heapSort(Integer[] array){
        buildHeap(array);
        System.out.println("建堆：");
        printTree(array,array.length);
        
        int lastIndex = array.length - 1;
        while (lastIndex > 0) {
            // 取出堆顶元素，将堆底放入堆顶。其实就是交换下标为0与lastIndex的数据
            CommonUtil.swap(array,0,lastIndex);
            // 只有一个元素时就不用调整堆了，排序结束
            if (--lastIndex == 0) {
                break;
            }
            // 调整堆
            adjustHeap(array,0,lastIndex);
            
            System.out.println("调整堆：");
            printTree(array,lastIndex + 1);
        }
    }
    
    /**
     * 用数组中的元素建堆
     */
    private static void buildHeap(Integer[] array){
        int lastIndex = array.length - 1;
        // (lastIndex-1)/2就是最后一个元素的根节点的下标，依次调整每棵子树
        for (int i = (lastIndex - 1) / VALUE_TWO; i >= 0; i--) {
            // 调整以下标i的元素为根的子树
            adjustHeap(array,i,lastIndex);
        }
    }
    
    /**
     * 调整以下标是rootIndex的元素为根的子树
     *
     * @param rootIndex 根的下标
     * @param lastIndex 堆中最后一个元素的下标
     */
    private static void adjustHeap(Integer[] array,int rootIndex,int lastIndex){
        int biggerIndex = rootIndex;
        // 左孩子
        int leftChildIndex = 2 * rootIndex + 1;
        // 右孩子
        int rightChildIndex = 2 * rootIndex + 2;
        // 存在右子节点，则必存在左子节点 这两步判断主要是找到左右孩子节点中找到比根大的节点的序号
        if (rightChildIndex <= lastIndex) {
            if (array[rootIndex] < array[leftChildIndex] || array[rootIndex] < array[rightChildIndex]) {
                // 子节点中存在比根更大的元素
                biggerIndex = array[leftChildIndex] < array[rightChildIndex] ? rightChildIndex : leftChildIndex;
            }
            
        } else if (leftChildIndex <= lastIndex) {
            // 只存在左子节点
            if (array[leftChildIndex] > array[rootIndex]) {
                // 左子节点更大
                biggerIndex = leftChildIndex;
            }
        }
        
        if (biggerIndex != rootIndex) {
            // 找到了比根更大的子节点
            CommonUtil.swap(array,rootIndex,biggerIndex);
            // 交换位置后可能会破坏子树，将焦点转向交换了位置的子节点，调整以它为根的子树
            adjustHeap(array,biggerIndex,lastIndex);
        }
    }
    
    /**
     * 将数组按照完全二叉树的形式打印出来
     */
    private static void printTree(Integer[] array,int len){
        // 树的层数
        int layers = (int)Math.floor(Math.log(len) / Math.log(2)) + 1;
        // 树的最大宽度
        int endSpacing = (int)Math.pow(2,layers) - 1;
        int spacing;
        int numberOfThisLayer;
        // 从第一层开始，逐层打印
        for (int i = 1; i <= layers; i++) {
            // 每层打印之前需要打印的空格数
            endSpacing = endSpacing / 2;
            // 元素之间应该打印的空格数
            spacing = 2 * endSpacing + 1;
            // 该层要打印的元素总数
            numberOfThisLayer = (int)Math.pow(2,i - 1);
            
            int j;
            for (j = 0; j < endSpacing; j++) {
                System.out.print("  ");
            }
            
            // 该层第一个元素对应的数组下标
            int beginIndex = (int)Math.pow(2,i - 1) - 1;
            for (j = 1; j <= numberOfThisLayer; j++) {
                System.out.print(array[beginIndex++] + "");
                // 打印元素之间的空格
                for (int k = 0; k < spacing; k++) {
                    System.out.print("  ");
                }
                // 已打印到最后一个元素
                if (beginIndex == len) {
                    break;
                }
            }
            
            System.out.println();
        }
        System.out.println();
    }
    
    private static void printTreeFunc(int[] array){
        int layer = (int)Math.floor(Math.log(array.length - 1));
    }
}
